#include <stdio.h>
#include <stdlib.h>



int seq_search(int array[] ,int n,int k, int seek_seq[]){
	//在顺序表array[0..n-1]中查找关键字为k的记录
	for (int i = 0;i<n; ++i) {
		seek_seq[i]=i;
		if(array[i]==k){
			return 0;
		}
	}
	return -1;
}

void r(int low,int high,int k,int array[],int *G,int seek_seq[],int location){
	//在按照递增顺序排列的有序表array[0..n-1]中进行二分查找，查找成功时返回0，失败时返回-1；
	//无论查找成功或失败，均通过修改seek_seq参数来返回依次查找的记录位置的序列，seek_seq元素已包含的元素个数等于n
	int middle=(low+high)/2;
	seek_seq[location]=middle;
	location++;
	if(low>high){
		*G=-1;
		return;
		printf("low>high\n");
	}
	if(low==middle){
		*G=high;
		return;
		printf("low==middle\n");
	}
	if(k>array[middle]){
		printf("k>array[middle]\n");
		printf("array[middle]:%d\n",array[middle]);
		printf("---------------\n");
		r(middle+1,high,k,array,&G,seek_seq,location);
	}
	if(k<array[middle]){
		printf("k<array[middle]\n");
		printf("array[middle]:%d\n",array[middle]);
		printf("---------------\n");
		r(low,middle-1,k,array,&G,seek_seq,location);
	}
	if(k==middle){
		printf("k=array[middle]\n");
		printf("array[middle]:%d\n",array[middle]);
		printf("---------------\n");
		*G=middle;
		return;
	}
	return;
}



int bin_search(int array[],int n,int k, int seek_seq[]){
	//在按照递增顺序排列的有序表array[0..n-1]中进行二分查找，查找成功时返回0，失败时返回-1；
	//无论查找成功或失败，均通过修改seek_seq参数来返回依次查找的记录位置的序列，seek_seq元素已包含的元素个数等于n
	int *G;
	r(0,n-1,k,array,&G,seek_seq,0);
	if(G=-1){
		return -1;
	} else
		return G;
	
}
int main() {
	
	int n=10;
	int array[] = {0,1,2,3,4,5,6,7,8,9};
	int seek_seq[10] ;
	
	for (int i = 0; i <n; ++i) {
		seek_seq[i]=-1;
	}
	int c =seq_search(array,n,6,seek_seq);
	printf("%d\n",c);
	for (int i = 0; i <n; ++i) {
		printf("%d,",seek_seq[i]);
	}
	for (int i = 0; i <n; ++i) {
		seek_seq[i]=-1;
	}
	printf("\n");
	int d= bin_search(array,n,4,seek_seq);
	printf("%d\n",d);
	for (int i = 0; i <n; ++i) {
		printf("%d,",seek_seq[i]);
	}
	return 0;
}


